package 力扣面试经典150;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-10
 * Time:14:34
 */

/**
 * 力扣面试经典150:30. 串联所有单词的子串
 * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
 *  s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
 *     例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
 * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
 * 示例 1：
 * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
 * 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
 * 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
 * 输出顺序无关紧要。返回 [9,0] 也是可以的。
 */
public class findSubstring {
    public static void main(String[] args) {
        findSubstring("barfoothefoobarman",new String[]{"foo","bar"});
    }
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        List<String> wordList = Arrays.asList(words);
        Collections.sort(wordList);

        //有几个单词
        int wordsLen = words.length;
        //每个单词长度
        int wordLen = words[0].length();
        //s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串 ,所以总长度
        int wordsLenSum = wordsLen * wordLen;
        if (s.length() < wordsLenSum) {
            return res;
        }
        for (int i = 0; i <= s.length() - wordsLenSum; i++) {
            String subStr = s.substring(i, i + wordsLenSum);
            List<String> tmpList = new ArrayList<>();
            for (int k = 0; k < subStr.length(); k = k + wordLen) {
                tmpList.add(subStr.substring(k, k + wordLen));
            }
            Collections.sort(tmpList);
            if (tmpList.equals(wordList)) {
                res.add(i);
            }
        }
        return res;
    }
}
